package a2;

import java.util.LinkedList;
import java.util.List;

/**
 * @version 2.1
 * @author Michael Sawaya
 */
public class Parser
{

    /**
     * The current location in the global token list.
     */
    private int currLocation;
    /**
     * The global token list
     */
    private List<Token> tokenList;
    /**
     * The current token in the global token list
     */
    private Token currentToken;

    /**
     * Checks the token list for another item
     * @return True if the list contains another item.
     */
    private boolean hasNextToken()
    {
        return tokenList.size() > currLocation;
    }

    /**
     * Returns the next token in the list.
     * @return The next token in the list.
     */
    private void nextToken()
    {
        if (!hasNextToken())
        {
            throw new NullPointerException("The list has no more items.");
        }
        else if (!currentToken.getType().equals("end-of-input"))
        {
            currentToken = tokenList.get(++currLocation);
        }
    }

    /**
     * Returns the current token in the list.
     * @return The current token in the list.
     */
    private void currToken()
    {
        currentToken = tokenList.get(currLocation);
    }

    /**
     * Returns true for a null object.
     * @param o The object to check.
     * @return  True for a null object.
     */
    private boolean isNull(Object o)
    {
        if (o == null)
        {
            throw new NullPointerException("Cannot parse null input");
        }
        return false;
    }

    /**
     * Takes a purported expression, represented as a String, and 
     * returns a syntax tree for the string. 
     * @param input Purported expression
     * @return Syntax Tree of the expression
     */
    public OrderedTree<Token> parse(String input)
    {
        if (input == null || input.equals(""))//checks for null/empty arguments
        {
            throw new IllegalArgumentException("Cannot parse null or empty string: " + input);
        }
        tokenList = Token.tokenize(input); //tokenizes the input for parsing
        if (tokenList == null || tokenList.size() <= 1) //checks for null/empty list
        {
            throw new NullPointerException("The token list is empty.");
        }
        currToken();
        //sets the location in the list to 0
        currLocation = 0;
        //calls to check if the list is a program
        return checkIsProgram();
    }

    /**
     * Parses the current location to match it with the grammar for a program
     * @return An Ordered Tree of Tokens representing a program
     */
    public OrderedTree<Token> checkIsProgram()
    {
        isNull(currentToken);
        //constructs children lists and expression tree
        List<OrderedTree<Token>> varOutput = new LinkedList<OrderedTree<Token>>();
        List<OrderedTree<Token>> funOutput = new LinkedList<OrderedTree<Token>>();
        OrderedTree<Token> expTree = new OrderedTree<Token>();
        while (hasNextToken())
        {
            if (currentToken.getType().equals("let")) //checks for variable definition
            {
                varOutput.add(checkIsVariableDefintion());
            }
            else
            {
                break;
            }
        }
        while (hasNextToken())
        {
            if (currentToken.getType().equals("define")) //checks for function definition
            {
                funOutput.add(checkIsFunctionDefinition());
            }
            else
            {
                break;
            }
        }
        String type = currentToken.getType();
        if (type.equals("apply") || type.equals("StringLiteral") || type.equals("Identifier")) //checks for expressions
        {
            expTree = checkIsExpression();
        }
        else //illegal position of token
        {
            throw new IllegalArgumentException("The input given was not "
                    + "legal in the predefined grammer at item #" + currLocation + ": " + currentToken);
        }
        //construct program tree
        OrderedTree<Token> varTree = new OrderedTree<Token>(new Token("variables"), varOutput);
        OrderedTree<Token> funTree = new OrderedTree<Token>(new Token("functions"), funOutput);
        List<OrderedTree<Token>> progList = new LinkedList<OrderedTree<Token>>();
        progList.add(varTree);
        progList.add(funTree);
        progList.add(expTree);
        return new OrderedTree<Token>(new Token("program"), progList); //uses program as root, and the list as children
    }

    /**
     * Parses the current location to match it with the grammar for a variable definition
     * @return An Ordered Tree of Tokens representing a variable definition
     */
    private OrderedTree<Token> checkIsVariableDefintion()
    {
        isNull(currentToken);
        Token let = currentToken;
        if (!let.getType().equals("let"))//checks for let terminator
        {
            throw new IllegalArgumentException("Expected \"let\" token, found " + let);
        }
        nextToken();
        Token identifier = currentToken;
        if (!identifier.getType().equals("Identifier"))//checks for identifier
        {
            throw new IllegalArgumentException("Expected Identifier, found " + identifier);
        }
        nextToken();
        //constructs the return tree
        List<OrderedTree<Token>> children = new LinkedList<OrderedTree<Token>>();
        children.add(new OrderedTree<Token>(identifier, null));
        children.add(checkIsExpression());//checks for expression
        return new OrderedTree<Token>(let, children); //used let as root and identifier and expression child
    }

    /**
     * Parses the current location to match it with the grammar for a function definition
     * @return An Ordered Tree of Tokens representing a function definition
     */
    private OrderedTree<Token> checkIsFunctionDefinition()
    {
        isNull(currentToken);
        Token define = currentToken;
        if (!define.getType().equals("define"))//checks for define terminator
        {
            throw new IllegalArgumentException("Expected \"define\" token, found " + define);
        }
        nextToken();
        //construct the tree
        List<OrderedTree<Token>> output = new LinkedList<OrderedTree<Token>>();
        output.add(checkIsSignature());//checks for sign.
        output.add(checkIsProgram());//checks for prog
        return new OrderedTree<Token>(define, output);//uses define as a root and the sign. and prog. as children
    }

    /**
     * Parses the current location to match it with the grammar for an expression
     * @return An Ordered Tree of Tokens representing an expression
     */
    private OrderedTree<Token> checkIsExpression()
    {
        isNull(currentToken);
        Token expression = currentToken;
        if (expression.getType().equals("StringLiteral") || expression.getType().equals("Identifier"))//checks for terminators
        {
            nextToken();
            return new OrderedTree<Token>(expression, null); //returns tree with only terminal expression as the root
            
        }
        else
        {
            return checkIfApplication();//checks for apply.
        }
    }

    /**
     * Parses the current location to match it with the grammar for a signature
     * @return An Ordered Tree of Tokens representing a signature
     */
    private OrderedTree<Token> checkIsSignature()
    {
        isNull(currentToken);
        Token rootIdentifier = currentToken;
        if (!rootIdentifier.getType().equals("Identifier"))//checks for initial identifier
        {
            throw new IllegalArgumentException("Expected Identifier, found " + rootIdentifier);
        }
        nextToken();
        if (!currentToken.getType().equals("("))//checks for parenthesis
        {
            throw new IllegalArgumentException("Expected token \"(\", found " + currentToken);
        }
        List<OrderedTree<Token>> output = new LinkedList<OrderedTree<Token>>();
        while (hasNextToken())
        {
            nextToken();
            if (currentToken.getType().equals("Identifier"))//checks for variable amounts of identifiers
            {
                output.add(new OrderedTree<Token>(currentToken, null));
            }
            else if (currentToken.getType().equals(")"))//checks for matching parenthesis
            {
                nextToken();
                return new OrderedTree<Token>(rootIdentifier, output);//returns tree with rootIdentifier as the root and the identifiers within the parenthesis as children
            }
            else
            {
                throw new IllegalArgumentException("Expected Identifier or \")\", found " + currentToken);
            }
        }
        throw new IllegalArgumentException("Illegal token found " + currentToken);
    }

    /**
     * Parses the current location to match it with the grammar for an application
     * @return An Ordered Tree of Tokens representing an application
     */
    private OrderedTree<Token> checkIfApplication()
    {
        isNull(currentToken);
        Token apply = currentToken;
        if (!apply.getType().equals("apply"))//checks for apply terminal symbol
        {
            throw new IllegalArgumentException("Expected \"apply\", found " + apply);
        }
        nextToken();
        OrderedTree<Token> funOutput = checkIsFunctionName();//checks for function names
        if (!currentToken.getType().equals("("))//checks for open parenthesis
        {
            throw new IllegalArgumentException("Expected \"(\", found " + currentToken);
        }
        nextToken();
        List<OrderedTree<Token>> expressions = new LinkedList<OrderedTree<Token>>();
        while (hasNextToken())
        {
            if (currentToken.getType().equals(")"))//check for closed parenthesis
            {
                nextToken();
                return new OrderedTree<Token>(funOutput.getRootData(), expressions);//return tree with the root function name and the expression children
            }
            else if (currentToken.getType().equals("end-of-input"))//checks for terminator symbol
            {
                throw new IllegalArgumentException("Expected expression or \")\", found " + currentToken);
            }
            else
            {
                expressions.add(checkIsExpression());//checks for expressions
            }
        }
        throw new IllegalArgumentException("Expected a token, found" + currentToken);
    }

    /**
     * Parses the current location to match it with the grammar for a function name
     * @return An Ordered Tree of Tokens representing a function name
     */
    private OrderedTree<Token> checkIsFunctionName()
    {
        isNull(currentToken);//checks for null token
        Token functionName = currentToken; 
        String type = functionName.getType();
        if (type.equals("Identifier") || type.equals("+") || type.equals("~"))//checks terminal symbols
        {
            nextToken();//moves to next token
            return new OrderedTree<Token>(new Token("FunctionName", functionName.getSpelling()), null);//returns tree with "FunctionName:spelling" and no leaves
        }
        else
        {
            throw new IllegalArgumentException("Expected Identifier, \"+\" or \"~\" token, found " + functionName);
        }

    }
}
